/**
 * 方法1：直接递归，中序遍历，设置一个当前的最大值，一直更新
 * 带有空叶子节点的二叉树，使用顺序存储方式
 * 判断这个树是否为二叉排序树
 * 
 * 这个是方法二：
 * 根节点在[0]，
 * 下标为i的节点，若左孩子存在，则下标为2i+1，有孩子为2i+2
 * 设置两个数组pmax和pmin
 * pmax和pmin保存的是以i为根的最大值和最小值
 * 二叉树[i]的值应该大于pmax[2i+1]的值
 * 二叉树[i]的值应该小于pmin[2i+2]的值
 * pmax和pmin初始化为树的元素
 */

#define MAX_SIZE 200
typedef struct{
    int SqBiTNode[MAX_SIZE];
    int ElemNum;
}SqBiTree;
#include<stdlib.h>

int judge(SqBiTree root){
    int k,m,*pmin,*pmax;
    //初始化最大值和最小值数组，都是原本数组的元素
    pmin=(int*) malloc(sizeof(int)*root.ElemNum);
    pmax=(int*)malloc(sizeof(int)*root.ElemNum);
    for(k=0;k<root.ElemNum;k++){
        pmin[k]=pmax[k]=root.SqBiTNode[k];
    }
    //这种方法是从下往上找的
    for(k=root.ElemNum-1;k>0;k--){//从最后一个节点向根遍历
        if(root.SqBiTNode[k]!=-1){
            m=(k-1)/2;//双亲
            //k为偶数，说明是右孩子
            if(k%2==1&&root.SqBiTNode[m]>pmax[k])//对于左子树，如果父节点的只值比左子树的大，那么跟新为较小的左子树的最小值
                pmin[m]=pmin[k];
            //k为奇数，说明是做孩子
            else if(k%2==0&&root.SqBiTNode[m]<pmin[k])//对于右子树，父子书值比较小，就更新为大的值
                pmax[m]=pmax[k];
            else return false;//如果不满足条件，那么直接返回false，不是二叉搜索树
        }
    }
    return true;//搜索完毕，返回true
}